#include "main/utils.h"
using namespace std;

int insertPos(const vector<int> &vec, const int &target) {
  int begin = 0;
  int end = vec.size() - 1;
  while (begin <= end) {
    int mid = begin + ((end - begin) >> 1);
    if (vec[mid] >= target && (mid == 0 || vec[mid - 1] < target)) {
      return mid;
    }
    if (vec[mid] > target) {
      end = mid - 1;
    } else if (vec[mid] < target) {
      begin = mid + 1;
    }
  }
  return vec.size();
}

int main() {
  vector<int> vec = {1, 3, 6, 8};
  cout << insertPos(vec, 3) << endl;
  cout << insertPos(vec, 5) << endl;
  cout << insertPos(vec, 9) << endl;

  return 0;
}
